package puzzle.common.solver;

import java.util.ArrayList;
import java.util.List;
import java.util.logging.Level;
import java.util.logging.Logger;

import puzzle.common.data.AbstractBoard;
import puzzle.common.data.HatanException;
import tomoto.util.Holder;

/**
 * TODO: holder usage should be rivisited TODO: symbol name shoule be revisited
 * TODO: use generics
 */
public abstract class AbstractSolver<B extends AbstractBoard<B>, P extends AbstractTopology, A extends AbstractAssumption> {
	private static Logger cs_logger = Logger.getLogger(AbstractSolver.class.getName());

	private List<BoardRule<B>> m_initialRules = new ArrayList<BoardRule<B>>();
	private List<BoardRule<B>> m_rules = new ArrayList<BoardRule<B>>();
	private List<TopologicalRule<B, P>> m_topologicalRules = new ArrayList<TopologicalRule<B, P>>();
	private FingerPrintDirectory m_fingerPrintDirectory = null;

	private SolverEventListener<SolverEvent<B>> m_listener;

	public AbstractSolver() {}

	protected final void useFingerPrint(int limit) {
		m_fingerPrintDirectory = new FingerPrintDirectory(limit);
	}

	//
	// Rule operations
	//

	protected final void addInitialRule(BoardRule<B> rule) {
		m_initialRules.add(rule);
	}

	protected final void addRule(BoardRule<B> rule) {
		m_rules.add(rule);
	}

	protected final void addTopologicalRule(TopologicalRule<B, P> rule) {
		m_topologicalRules.add(rule);
	}

	protected final boolean applyInitialRules(B b) throws HatanException, SolverAbortingException {
		boolean isChanged = false;
		for (BoardRule<B> rule : m_initialRules) {
			boolean isLocallyChanged = rule.apply(b);
			fireProgressEvent(SolverEvent.createTheoryRuleEvent(b, rule, isLocallyChanged));
			isChanged |= isLocallyChanged;
		}
		return isChanged;
	}

	protected final boolean applyRules(B b) throws HatanException, SolverAbortingException {
		boolean isChanged = false;
		for (BoardRule<B> rule : m_rules) {
			boolean isLocalyChanged = rule.apply(b);
			fireProgressEvent(SolverEvent.createTheoryRuleEvent(b, rule, isLocalyChanged));
			isChanged |= isLocalyChanged;
		}
		return isChanged;
	}

	protected final boolean applyTopologicalRules(B b, P topology) throws HatanException,
			SolverAbortingException {
		boolean isChanged = false;
		for (TopologicalRule<B, P> rule : m_topologicalRules) {
			boolean isLocalyChanged = rule.apply(b, topology);
			fireProgressEvent(SolverEvent.createTheoryRuleEvent(b, rule, isLocalyChanged));
			isChanged |= isLocalyChanged;
		}
		return isChanged;
	}

	//
	// Listener operations
	//

	public final void setSolverEventListener(SolverEventListener<SolverEvent<B>> listener) {
		m_listener = listener;
	}

	protected final void fireProgressEvent(SolverEvent<B> event) throws SolverAbortingException {
		if (m_listener != null) {
			m_listener.onProgress(event);
		}
	}

	//
	// Solution process
	//

	public SolutionState solveAll(B b) throws SolverAbortingException {
		try {
			applyInitialRules(b);
		} catch (HatanException ex) {
			return SolutionState.HATAN;
		}

		Holder<P> topologyHld = new Holder<P>();
		SolutionState s = solveTheoritically(b, topologyHld);
		if (s == SolutionState.INCOMPLETE) {
			return assumeAndSolveRecursively(b, topologyHld, 1, null);
		} else {
			return s;
		}
	}

	// Based on theory

	public SolutionState solveTheoritically(B b, Holder<P> topology) throws SolverAbortingException {
		try {
			boolean isChanged = true;
			do {
				b.snapshotDirtyFlags();
				fireProgressEvent(SolverEvent.createTheoryStepEvent(b, isChanged));

				while (applyRules(b)) {
					b.snapshotDirtyFlags();
					fireProgressEvent(SolverEvent.createTheoryStepEvent(b, true));
				}
				topology.obj = analyzeTopology(b);
			} while (isChanged = applyTopologicalRules(b, topology.obj));

			fireProgressEvent(SolverEvent.createTheoryStepEvent(b, isChanged));
			fireProgressEvent(SolverEvent.createTheoryWholeEvent(b));

			return checkSolutionState(b, topology.obj);
		} catch (HatanException ex) {
			fireProgressEvent(SolverEvent.createTheoryWholeEvent(b));
			return SolutionState.HATAN;
		}
	}

	protected abstract P analyzeTopology(B b);

	protected abstract SolutionState checkSolutionState(B b, P topology);

	// Based on assumption

	private SolutionState assumeAndSolveRecursively(B b0, Holder<P> topologyHld0, int depth,
			A prevAssumption) throws SolverAbortingException {
		cs_logger.log(Level.FINE, "Assumption depth {0}", depth);

		List<BoardSnapshot<B, P, A>> bss = new ArrayList<BoardSnapshot<B, P, A>>();
		List<A> hatanAssumptions = new ArrayList<A>();

		while (true) {
			bss.clear();

			List<A> assumptions = assume(b0, topologyHld0.obj, prevAssumption);

			if (cs_logger.isLoggable(Level.FINE)) {
				cs_logger.log(Level.FINE, "Assumed " + assumptions.size() + " "
						+ assumptions.toString());
			}

			if (assumptions.size() == 0) {
				return checkSolutionState(b0, topologyHld0.obj);
			}

			int hatanCount = 0;
			boolean isChanged = false;
			for (A a : assumptions) {
				if (isAlreadyTried(bss, b0, a)) {
					continue;
				}
				B b = b0.dup();
				SolutionState ss;
				Holder<P> topologyHld = new Holder<P>();
				try {
					applyAssumption(bss, b, a);
					ss = solveTheoritically(b, topologyHld);
				} catch (HatanException ex) {
					ss = SolutionState.HATAN;
				}

				switch (ss) {
				case COMPLETE:
					b0.copyFrom(b);
					topologyHld0.obj = topologyHld.obj;
					return ss;
				case INCOMPLETE:
					BoardSnapshot<B, P, A> bs = new BoardSnapshot<B, P, A>(b, topologyHld.obj, ss,
							a);
					bss.add(bs);
					break;
				case HATAN:
					hatanCount++;
					isChanged = true;
					hatanAssumptions.add(a);
					SolutionState ss2;
					try {
						excludeAssumption(b0, a);
						ss2 = solveTheoritically(b0, topologyHld0);
					} catch (HatanException ex) {
						ss2 = SolutionState.HATAN;
					}
					if (ss2 != SolutionState.INCOMPLETE) {
						return ss2;
					}
					break;
				}
			}

			if (isChanged) {
				cs_logger.log(Level.FINE, "Excluded " + hatanCount + " and try again");
			} else {
				cs_logger.log(Level.FINE, "Survived " + bss.size());
				break;
			}

		}

		sortBoardSnapshots(bss);

		for (BoardSnapshot<B, P, A> bs : bss) {
			assert bs.getSolutionState() == SolutionState.INCOMPLETE;
			B b = bs.getBoard();
			Holder<P> topologyHld = new Holder<P>(bs.getTopology());

			if (m_fingerPrintDirectory != null && m_fingerPrintDirectory.check(getFingerPrint(b))) {
				cs_logger.log(Level.FINE, "Skipping " + bs.getAssumption()
						+ " because of duplication");
				continue;
			}

			cs_logger.log(Level.FINE, "Drilling down to " + bs.getAssumption());
			SolutionState ss = assumeAndSolveRecursively(b, topologyHld, depth + 1, bs
					.getAssumption());

			switch (ss) {
			case COMPLETE:
				b0.copyFrom(b);
				topologyHld0.obj = topologyHld.obj;
				return ss;
			case HATAN:
				cs_logger.log(Level.FINE, "Excluded " + bs.getAssumption());
				hatanAssumptions.add(bs.getAssumption());
				break;
			case INCOMPLETE:
				SolutionState ss2;
				try {
					excludeAssumption(b0, bs.getAssumption());
					ss2 = solveTheoritically(b0, topologyHld0);
				} catch (HatanException ex) {
					ss2 = SolutionState.HATAN;
				}
				if (ss2 != SolutionState.INCOMPLETE) {
					return ss2;
				}
				break;
			}
		}

		return SolutionState.HATAN;
	}

	/**
	 * 盤面の状態の指紋を取得して返す。指紋を使う場合、サブクラスで実装。
	 * 
	 * @param b 盤面
	 * @return 指紋。一致比較演算が実装されていること。
	 */
	protected Object getFingerPrint(B b) {
		return null;
	}

	protected abstract List<A> assume(B b, P topology, A prevAssumption);

	protected abstract boolean isAlreadyTried(List<BoardSnapshot<B, P, A>> bss, B b, A a);

	protected abstract void applyAssumption(List<BoardSnapshot<B, P, A>> bss, B b, A a)
			throws HatanException;

	protected abstract void sortBoardSnapshots(List<BoardSnapshot<B, P, A>> bss);

	protected abstract void excludeAssumption(B b, A a) throws HatanException;

}
